1. Technical Field
The present invention relates to interactions between transcription factor binding, and more particularly, to a sparse high-order Boltzmann Machine for identifying combinatorial interactions between transcription factors.
2. Description of the Related Art
Identifying combinatorial relationships between transcription factors (TFs) maps the data mining task of discovering the statistical dependency between categorical variables. Model selection in high dimensional discrete case has been a traditionally challenging task. Recently, an approach of generative structure learning is to impose an L1 penalty on the parameters of the model, and to find a Maximum a posteriori probability (MAP) parameter estimate. The L1 penalty causes many of the parameters, corresponding to edge features, to go to zero, resulting in a sparse graph.
This was originally explored for modeling continuous data with Gaussian Markov Random Fields (MRFs) in two variants. In the Markov Blanket (MB) variant, the method learns a dependency network p(yi|y−i) by fitting d separate regression problems (independently regressing the label of each of the d nodes on all other nodes), and L1-regularization is used to select a sparse neighbor set. Although one can show this is a consistent estimator of topology, the resulting model is not a joint density estimator p(y). In the Random Field (RF) variant, L1-regularization is applied to the elements of the precision matrix to yield sparsity. While the RF variant is more computationally expensive, it yields both a structure and a parameterized model (while the MB variant yields only a structure).
The discrete case is much harder than the Gaussian case, partially because of the potentially intractable normalizing constant. Another complicating factor in the discrete case is that each edge may have multiple parameters. This arises in multistate models as well as conditional random Fields. For modeling discrete data, algorithms have been proposed for the specific case where the data is binary and the edges have Ising potentials, and in the binary-Ising case, there is a 1:1 correspondence between parameters and edges, and this L1 approach is suitable. However, in more general scenarios (including any combination of multi-class MRFs, non-Ising edge potentials), where many features are associated with each edge, there exists a need for block-L1 systems and methods that jointly reduce groups of parameters to zero at the same time to achieve sparsity. Moreover, prior approaches do not reveal higher-order dependencies between variables, such as how the binding activity of one TF can affect the relationship between two other TFs.